UINT32_MAX = (1 << 32) - 1


class MT:
    def __init__(self, seed):
        self.state = [0] * 625
        self.index = 625
        self.state[0] = seed & 0xffffffff

        int0 = seed & 0xffff
        int1 = (seed >> 16) & 0xffff

        for i in range(1, 624):
            int0 ^= int1 >> 14

            carry = (0x8965 * int0) + i
            int1 = ((0x8965 * int1) + (0x6C07 * int0) + (carry >> 16)) & 0xffff
            int0 = carry & 0xffff

            self.state[i] = (int1 << 16) | int0
        self.index = 624

    @staticmethod
    def twist(m, u, v):
        y = (u & 0x80000000) | (v & 0x7fffffff)
        return m ^ ((y >> 1) & 0x7fffffff) ^ (0x9908b0df * (v & 1))

    def int32(self):
        if self.index >= 624:
            if self.index == 625:
                self.__init__(5489)

            for i in range(227):
                self.state[i] = self.twist(self.state[i + 397], self.state[i], self.state[i + 1])
            for i in range(227, 623):
                self.state[i] = self.twist(self.state[i - 227], self.state[i], self.state[i + 1])

            self.state[623] = self.twist(self.state[396], self.state[623], self.state[0])
            self.index = 0;

        y = self.state[self.index]
        self.index += 1
        y ^= (y >> 11) & 0x001fffff
        y ^= (y << 7) & 0x9d2c5680
        y ^= (y << 15) & 0xefc60000
        y ^= (y >> 18) & 0x00003fff

        return y

    def int31(self):
        return (self.int32() >> 1) & 0x7fffffff

    def rand_range32(self, umax):

        result = self.int32()

        # Special case where no modulus is required
        if umax == UINT32_MAX:
            return result

        # Increment the max so the range is inclusive of max
        umax += 1

        # Powers of two are not biased
        if (umax & (umax - 1)) == 0:
            return result & (umax - 1)

        #  Ceiling under which UINT32_MAX % max == 0
        limit = UINT32_MAX - (UINT32_MAX % umax) - 1

        # Discard numbers over the limit to avoid modulo bias
        while result > limit:
            result = self.int32()

        return result % umax

    def mt_rand(self, min, max):
        return min + self.rand_range32(max)
